package jianzhiOffer;

import java.util.HashMap;
import java.util.Map;

//剑指 Offer 10- I. 斐波那契数列
public class Num10_I_fib {

    //
    static public int fib(int n){

        int [] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        for (int i = 3; i <= n ; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println(fib(6));
    }



//    private Map<Integer,Integer> map = new HashMap<>();
//    public int fib(int n) {
//        if (n==0){
//            return 0;
//        }
//        if (n==1||n==2){
//            return 1;
//        }
//        int prev = 0;
//        if (map.containsKey(n-1)){
//            prev = map.get(n-1);
//
//        }else {
//            prev = fib(n-1);
//            map.put(n-1,prev);
//        }
//        int cur = 0;
//        if (map.containsKey(n-2)){
//            cur = map.get(n-2);
//        }else {
//            cur = fib(n-2);
//            map.put(n-2,cur);
//        }
//        return prev+cur;
//
//
//    }
//

}
